package DFS_BFS;

import 递归.LeetCode226;

/**
 * @PackageName: DFS_BFS
 * @ClassName: LeetCode993
 * @Author: chen jinxu
 * @Date: 2022/3/12 21:36
 * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
 * 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
 * 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
 * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
 */
public class LeetCode993 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2, null, new TreeNode(4)),
                new TreeNode(3, null, new TreeNode(5)));
        boolean result = isCousins(root, 5, 4);
        System.out.println(result);
    }

    public static boolean isCousins(TreeNode root, int x, int y) {
        int[] left = dfs(root, x, null, 0);
        int[] right = dfs(root, y, null, 0);
        return left[0] != right[0] && left[1] == right[1];
    }

    private static int[] dfs(TreeNode node, int x, TreeNode fatherNode, int depth) {
        if (node == null) {
            // 表示没有找到
            return new int[]{-1, -1};
        }
        if (node.val == x) {
            return new int[]{fatherNode == null ? 1: fatherNode.val, depth};
        }
        int[] left = dfs(node.left, x, node, depth++);
        if (left[0] == -1) {
            return left;
        }
        int[] right = dfs(node.right, x, node, depth++);
        return right;
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}
